home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / cmds / find / dist / find / tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-14  |  12.4 KB  |  437 lines
  1. /* tree.c -- helper functions to build and evaluate the expression tree.
  2.    Copyright (C) 1987, 1990, 1991 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2, or (at your option)
  7.    any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17.  
  18. #include <stdio.h>
  19. #include <sys/types.h>
  20. #include "defs.h"
  21.  
  22. boolean pred_and ();
  23. boolean pred_comma ();
  24. boolean pred_name ();
  25. boolean pred_or ();
  26. boolean pred_path ();
  27. boolean pred_regex ();
  28.  
  29. struct predicate *scan_rest ();
  30. void merge_pred ();
  31. struct predicate *set_new_parent ();
  32.  
  33. /* Return a pointer to a tree that represents the
  34.    expression prior to non-unary operator *INPUT.
  35.    Set *INPUT to point at the next input predicate node.
  36.  
  37.    Only accepts the following:
  38.    
  39.    <victim>
  40.    expression        [operators of higher precedence]
  41.    <uni_op><victim>
  42.    (arbitrary expression)
  43.    <uni_op>(arbitrary expression)
  44.    
  45.    In other words, you can not start out with a bi_op or close_paren.
  46.  
  47.    If the following operator (if any) is of a higher precedence than
  48.    PREV_PREC, the expression just nabbed is part of a following
  49.    expression, which really is the expression that should be handed to
  50.    our caller, so get_expr recurses. */
  51.  
  52. struct predicate *
  53. get_expr (input, prev_prec)
  54.      struct predicate **input;
  55.      short prev_prec;
  56. {
  57.   struct predicate *next;
  58.  
  59.   if (*input == NULL)
  60.     error (1, 0, "invalid expression");
  61.   switch ((*input)->p_type)
  62.     {
  63.     case NO_TYPE:
  64.     case BI_OP:
  65.     case CLOSE_PAREN:
  66.       error (1, 0, "invalid expression");
  67.       break;
  68.  
  69.     case VICTIM_TYPE:
  70.       next = *input;
  71.       *input = (*input)->pred_next;
  72.       break;
  73.  
  74.     case UNI_OP:
  75.       next = *input;
  76.       *input = (*input)->pred_next;
  77.       next->pred_right = get_expr (input, NEGATE_PREC);
  78.       break;
  79.  
  80.     case OPEN_PAREN:
  81.       *input = (*input)->pred_next;
  82.       next = get_expr (input, NO_PREC);
  83.       if ((*input == NULL)
  84.       || ((*input)->p_type != CLOSE_PAREN))
  85.     error (1, 0, "invalid expression");
  86.       *input = (*input)->pred_next;    /* move over close */
  87.       break;
  88.  
  89.     default:
  90.       error (1, 0, "oops -- invalid expression type!");
  91.       break;
  92.     }
  93.  
  94.   /* We now have the first expression and are positioned to check
  95.      out the next operator.  If NULL, all done.  Otherwise, if
  96.      PREV_PREC < the current node precedence, we must continue;
  97.      the expression we just nabbed is more tightly bound to the
  98.      following expression than to the previous one. */
  99.   if (*input == NULL)
  100.     return (next);
  101.   if ((int) (*input)->p_prec > (int) prev_prec)
  102.     {
  103.       next = scan_rest (input, next, prev_prec);
  104.       if (next == NULL)
  105.     error (1, 0, "invalid expression");
  106.     }
  107.   return (next);
  108. }
  109.  
  110. /* Scan across the remainder of a predicate input list starting
  111.    at *INPUT, building the rest of the expression tree to return.
  112.    Stop at the first close parenthesis or the end of the input list.
  113.    Assumes that get_expr has been called to nab the first element
  114.    of the expression tree.
  115.    
  116.    *INPUT points to the current input predicate list element.
  117.    It is updated as we move along the list to point to the
  118.    terminating input element.
  119.    HEAD points to the predicate element that was obtained
  120.    by the call to get_expr.
  121.    PREV_PREC is the precedence of the previous predicate element. */
  122.  
  123. struct predicate *
  124. scan_rest (input, head, prev_prec)
  125.      struct predicate **input;
  126.      struct predicate *head;
  127.      short prev_prec;
  128. {
  129.   struct predicate *tree;    /* The new tree we are building. */
  130.  
  131.   if ((*input == NULL) || ((*input)->p_type == CLOSE_PAREN))
  132.     return (NULL);
  133.   tree = head;
  134.   while ((*input != NULL) && ((int) (*input)->p_prec > (int) prev_prec))
  135.     {
  136.       switch ((*input)->p_type)
  137.     {
  138.     case NO_TYPE:
  139.     case VICTIM_TYPE:
  140.     case UNI_OP:
  141.     case OPEN_PAREN:
  142.       error (1, 0, "invalid expression");
  143.       break;
  144.  
  145.     case BI_OP:
  146.       (*input)->pred_left = tree;
  147.       tree = *input;
  148.       *input = (*input)->pred_next;
  149.       tree->pred_right = get_expr (input, tree->p_prec);
  150.       break;
  151.  
  152.     case CLOSE_PAREN:
  153.       return (tree);
  154.  
  155.     default:
  156.       error (1, 0, "oops -- invalid expression type!");
  157.       break;
  158.     }
  159.     }
  160.   return (tree);
  161. }
  162.  
  163. /* Optimize the ordering of the predicates in the tree.  Rearrange
  164.    them to minimize work.  Strategies:
  165.    * Evaluate predicates that don't need inode information first;
  166.      the predicates are divided into 1 or more groups separated by
  167.      predicates (if any) which have "side effects", such as printing.
  168.      The grouping implements the partial ordering on predicates which
  169.      those with side effects impose.
  170.    * Place -name, -path, and -regex at the front of a group, with
  171.      -name and -path ahead of -regex.  Predicates that are moved to the
  172.      front of a group by definition do not have side effects.
  173.  
  174.      This routine "normalizes" the predicate tree by ensuring that
  175.      all expression predicates have AND (or OR or COMMA) parent nodes
  176.      which are linked along the left edge of the expression tree.
  177.      This makes manipulation of subtrees easier.  
  178.  
  179.      EVAL_TREEP points to the root pointer of the predicate tree
  180.      to be rearranged.  opt_expr may return a new root pointer there.
  181.      Return true if the tree contains side effects, false if not. */
  182.  
  183. boolean
  184. opt_expr (eval_treep)
  185.      struct predicate **eval_treep;
  186. {
  187.   /* List of -name and -path predicates to move. */
  188.   struct predicate *name_list = NULL;
  189.   struct predicate *end_name_list = NULL;
  190.   /* List of -regex predicates to move. */
  191.   struct predicate *regex_list = NULL;
  192.   struct predicate *end_regex_list = NULL;
  193.   struct predicate *curr;
  194.   struct predicate **prevp;    /* Address of `curr' node. */
  195.   struct predicate **last_sidep; /* Last predicate with side effects. */
  196.   PFB pred_func;
  197.   enum predicate_type p_type;
  198.   boolean has_side_effects = false; /* Return value. */
  199.   enum predicate_precedence prev_prec, /* precedence of last BI_OP in branch */
  200.                 biop_prec; /* topmost BI_OP precedence in branch */
  201.  
  202.  
  203.   if (eval_treep == NULL || *eval_treep == NULL)
  204.     return (false);
  205.  
  206.   /* Set up to normalize tree as a left-linked list of ANDs or ORs.
  207.      Set `curr' to the leftmost node, `prevp' to its address, and
  208.      `pred_func' to the predicate type of its parent. */
  209.   prevp = eval_treep;
  210.   prev_prec = AND_PREC;
  211.   curr = *prevp;
  212.   while (curr->pred_left != NULL)
  213.     {
  214.       prevp = &curr->pred_left;
  215.       prev_prec = curr->p_prec;    /* must be a BI_OP */
  216.       curr = curr->pred_left;
  217.     }
  218.  
  219.   /* Link in the appropriate BI_OP for the last expression, if needed. */
  220.   if (curr->p_type != BI_OP)
  221.     set_new_parent (curr, prev_prec, prevp);
  222.   
  223. #ifdef DEBUG
  224.   /* Normalized tree. */
  225.   printf ("Normalized Eval Tree:\n");
  226.   print_tree (*eval_treep, 0);
  227. #endif
  228.  
  229.   /* Rearrange the predicates. */
  230.   prevp = eval_treep;
  231.   if ((*prevp) && (*prevp)->p_type == BI_OP)
  232.     biop_prec = (*prevp)->p_prec;
  233.   while ((curr = *prevp) != NULL)
  234.     {
  235.       /* If there is a BI_OP of different precedence from the first
  236.      in the pred_left chain, create a new parent of the
  237.      original precedence, link the new parent to the left of the
  238.      previous and link CURR to the right of the new parent. 
  239.      This preserves the precedence of expressions in the tree
  240.      in case we rearrange them. */
  241.       if (curr->p_type == BI_OP)
  242.     {
  243.           if (curr->p_prec != biop_prec)
  244.         curr = set_new_parent(curr, biop_prec, prevp);
  245.           else
  246.         biop_prec = curr->p_prec;
  247.     }
  248.       
  249.       /* See which predicate type we have. */
  250.       p_type = curr->pred_right->p_type;
  251.       pred_func = curr->pred_right->pred_func;
  252.  
  253.       switch (p_type)
  254.     {
  255.     case NO_TYPE:
  256.     case VICTIM_TYPE:
  257.       /* If it's one of our special victims, move it to the
  258.          front of the list for that victim. */
  259.       if (pred_func == pred_name || pred_func == pred_path)
  260.         {
  261.           *prevp = curr->pred_left;
  262.           curr->pred_left = name_list;
  263.           name_list = curr;
  264.  
  265.           if (end_name_list == NULL)
  266.         end_name_list = curr;
  267.  
  268.           continue;
  269.         }
  270.  
  271.       if (pred_func == pred_regex)
  272.         {
  273.           *prevp = curr->pred_left;
  274.           curr->pred_left = regex_list;
  275.           regex_list = curr;
  276.  
  277.           if (end_regex_list == NULL)
  278.         end_regex_list = curr;
  279.  
  280.           continue;
  281.         }
  282.  
  283.       break;
  284.  
  285.     case UNI_OP:
  286.       /* For NOT, check the expression trees below the NOT. */
  287.       curr->pred_right->side_effects
  288.         = opt_expr (&curr->pred_right->pred_right);
  289.       break;
  290.  
  291.     case BI_OP:
  292.       /* For nested AND or OR, recurse (AND/OR form layers on the left of
  293.          the tree), and continue scanning this level of AND or OR. */
  294.       curr->pred_right->side_effects = opt_expr (&curr->pred_right);
  295.       break;
  296.  
  297.       /* At this point, get_expr and scan_rest have already removed
  298.          all of the user's parentheses. */
  299.  
  300.     default:
  301.       error (1, 0, "oops -- invalid expression type!");
  302.       break;
  303.     }
  304.  
  305.       if (curr->pred_right->side_effects == true)
  306.     {
  307.       last_sidep = prevp;
  308.  
  309.       /* Incorporate lists and reset list pointers for this group.  */
  310.       if (name_list != NULL)
  311.         {
  312.           merge_pred (name_list, end_name_list, last_sidep);
  313.           name_list = end_name_list = NULL;
  314.         }
  315.  
  316.       if (regex_list != NULL)
  317.         {
  318.           merge_pred (regex_list, end_regex_list, last_sidep);
  319.           regex_list = end_regex_list = NULL;
  320.         }
  321.  
  322.       has_side_effects = true;
  323.     }
  324.  
  325.       prevp = &curr->pred_left;
  326.     }
  327.  
  328.   /* Do final list merges. */
  329.   last_sidep = prevp;
  330.   if (name_list != NULL)
  331.     merge_pred (name_list, end_name_list, last_sidep);
  332.   if (regex_list != NULL)
  333.     merge_pred (regex_list, end_regex_list, last_sidep);
  334.  
  335.   return (has_side_effects);
  336. }
  337.  
  338. /* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence
  339.    HIGH_PREC. */
  340.  
  341. struct predicate *
  342. set_new_parent (curr, high_prec, prevp)
  343.      struct predicate *curr;
  344.      enum predicate_precedence high_prec;
  345.      struct predicate **prevp;
  346. {
  347.   struct predicate *new_parent;
  348.  
  349.   new_parent = (struct predicate *) xmalloc (sizeof (struct predicate));
  350.   new_parent->p_type = BI_OP;
  351.   new_parent->p_prec = high_prec;
  352.   new_parent->need_stat = false;
  353.  
  354.   switch (high_prec)
  355.     {
  356.     case COMMA_PREC:
  357.       new_parent->pred_func = pred_comma;
  358.       break;
  359.     case OR_PREC:
  360.       new_parent->pred_func = pred_or;
  361.       break;
  362.     case AND_PREC:
  363.       new_parent->pred_func = pred_and;
  364.       break;
  365.     }
  366.   
  367.   new_parent->side_effects = false;
  368.   new_parent->args.str = NULL;
  369.   new_parent->pred_next = NULL;
  370.  
  371.   /* Link in new_parent.
  372.      Pushes rest of left branch down 1 level to new_parent->pred_right. */
  373.   new_parent->pred_left = NULL;
  374.   new_parent->pred_right = curr;
  375.   *prevp = new_parent;
  376.  
  377. #ifdef    DEBUG
  378.   new_parent->p_name = (char *) find_pred_name (new_parent->pred_func);
  379. #endif /* DEBUG */
  380.  
  381.   return (new_parent);
  382. }
  383.  
  384. /* Merge the predicate list that starts at BEG_LIST and ends at END_LIST
  385.    into the tree at LAST_P. */
  386.  
  387. void
  388. merge_pred (beg_list, end_list, last_p)
  389.      struct predicate *beg_list, *end_list, **last_p;
  390. {
  391.   end_list->pred_left = *last_p;
  392.   *last_p = beg_list;
  393. }
  394.  
  395. /* Find the first node in expression tree TREE that requires
  396.    a stat call and mark the operator above it as needing a stat
  397.    before calling the node.   Since the expression precedences 
  398.    are represented in the tree, some preds that need stat may not
  399.    get executed (because the expression value is determined earlier.)
  400.    So every expression needing stat must be marked as such, not just
  401.    the earliest, to be sure to obtain the stat.  This still guarantees 
  402.    that a stat is made as late as possible.  Return true if the top node 
  403.    in TREE requires a stat, false if not. */
  404.  
  405. boolean
  406. mark_stat (tree)
  407.      struct predicate *tree;
  408. {
  409.   /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
  410.      to find the first predicate for which the stat is needed. */
  411.   switch (tree->p_type)
  412.     {
  413.     case NO_TYPE:
  414.     case VICTIM_TYPE:
  415.       return tree->need_stat;
  416.  
  417.     case UNI_OP:
  418.       if (mark_stat (tree->pred_right))
  419.     tree->need_stat = true;
  420.       return (false);
  421.  
  422.     case BI_OP:
  423.       /* ANDs and ORs are linked along ->left ending in NULL. */
  424.       if (tree->pred_left != NULL)
  425.     mark_stat (tree->pred_left);
  426.  
  427.       if (mark_stat (tree->pred_right))
  428.     tree->need_stat = true;
  429.  
  430.       return (false);
  431.  
  432.     default:
  433.       error (1, 0, "oops -- invalid expression type!");
  434.       return (false);
  435.     }
  436. }
  437.